package countSort;

/**
 *  时间复杂度：O(N+范围）
 *  空间复杂度：O(范围）
 *  稳定性：稳定
 *
 */

public class MyCountSort {
    public static void countSort(int[] array) {
        int maxValue = array[0];
        int minValue = array[0];

        for (int val : array) {
            //确定数组最小值
            if (val < minValue) {
                minValue = val;
            }
            //确定数组最大值
            if (val > maxValue) {
                maxValue = val;
            }
        }
        int len = maxValue - minValue + 1;
        int[] count = new int[len];

        //遍历array数组进行遍历
        for (int val : array) {
            count[val - minValue]++;
        }

        int indexArray = 0; //array数组的下标
        for (int i = 0; i < count.length; i++) {

            while(count[i] != 0) {
                array[indexArray] = i + minValue;
                indexArray++;
                count[i]--;
            }
        }
    }
}
